package practice_2025_11.practice_11_21;

import java.util.HashSet;
import java.util.Set;


class Solution {
    /**
     * 长度为 3 的不同回文子序列 —— 枚举两侧字符
     * aba -> 找到最左和最右的相同字符 ch, 再计算中间有多少个不同字符
     * @param s
     * @return
     */
    public int countPalindromicSubsequence(String s) {
        // 枚举两侧字符
        int count = 0;
        int len = s.length();
        for(char ch = 'a'; ch <= 'z'; ch++) {
            int left = 0, right = len - 1;
            while(left < len && s.charAt(left) != ch) {
                left++;
            }
            while(right > left && s.charAt(right) != ch) {
                right--;
            }
            // 存在回文串
            if (right - left >= 2) {
                Set<Character> hash = new HashSet<>();
                for(int i = left + 1; i < right; i++) {
                    hash.add(s.charAt(i));
                }
                count += hash.size();
            }
        }
        return count;
    }

    /**
     * 长度为 3 的不同回文子序列 —— 枚举中间字符
     * aba -> 计算中间字符(b) 两侧有多少不同的 相同字符对,
     * 中间字符可能会重复, 因此要更新结果为最大的字符对数
     * 计算中间字符两次不同字符对：使用前缀和和后缀和
     * 前缀和prev[i]: i 位置之前有多少个不同的字符(不同的字符使用不同的比特位表示)
     * 后缀和last[i]: i 位置之后有多少个不同的字符
     * 使用 ans[26] 来统计中间字符 ans[i] 的两侧不同的 相同字符对数
     * @param s
     * @return
     */
    public int countPalindromicSubsequence2(String s) {
        // 枚举中间字符
        int len = s.length();
        int[] prev = new int[len];
        int[] last = new int[len];
        // 初始化前缀和
        for(int i = 1; i < len; i++) {
            int index = s.charAt(i - 1) - 'a';
            prev[i] = prev[i - 1];
            prev[i] |= (1 << index);
        }
        // 初始化后缀和
        for(int i = len - 2; i >= 0; i--) {
            int index = s.charAt(i + 1) - 'a';
            last[i] = last[i + 1];
            last[i] |= (1 << index);
        }
        int count = 0;
        int[] ans = new int[26];
        for(int i = 1; i < len - 1; i++) {
            ans[s.charAt(i) - 'a'] |= ( prev[i] & last[i]);
        }
        for(int i = 0; i < ans.length; i++) {
            count += Integer.bitCount(ans[i]);
        }
        return count;
    }
}